﻿#include <iostream>
#include <assert.h>

/**
 * 查找两个有序的等规模数组的上中位数
 * 举例: 两个长度为4的数组，中位数是两个数组数字有序排列成一个数组之后的第3元素(从0开始);
 * 两个长度为5的数组，中位数是两个数组数字有序排列成一个数组之后的第5元素(从0开始);
 */
static int findUpMiddleNumber(const int* arr1, const int start1, const int end1, const int* arr2, const int start2, const int end2)
{
	assert((end1 - start1 == end2 - start2) && "arr Must be equal size!");

	int count = end1 - start1 + 1;
	int middle1;
	int middle2;
	// 等规模
	if (count % 2 == 0)
	{
		middle1 = start1 + count / 2 - 1;
		middle2 = start2 + count / 2 - 1;
	}
	else
	{
		middle1 = start1 + count / 2;
		middle2 = start2 + count / 2;
	}
	
	if (arr1[middle1] == arr2[middle2]) return arr1[middle1];

	if (count % 2 == 0)
	{
		// 偶数个
		if (count == 2)
		{
			if (arr2[middle2] <= arr1[middle1])
			{
				if (arr2[end2] <= arr1[start1])
				{
					return arr2[end2];
				}
				else
				{
					return arr1[middle1];
				}
			}
			else
			{
				if (arr1[end1] <= arr2[start2])
				{
					return arr1[end1];
				}
				else
				{
					return arr2[middle2];
				}
			}
		}
		else
		{
			if (arr1[middle1] <= arr2[middle2])
			{
				return findUpMiddleNumber(arr1, middle1 + 1, end1, arr2, start2, middle2);
			}
			else
			{
				return findUpMiddleNumber(arr1, start1, middle1, arr2, middle2 + 1, end2);
			}
		}
	}
	else
	{
		// 奇数个
		if (count == 1)
		{
			return arr1[start1] <= arr2[start2] ? arr1[start1] : arr2[start2];
		}
		else
		{
			if (arr2[middle2] <= arr1[middle1])
			{
				if (arr2[middle2] > arr1[middle1 - 1])
				{
					return arr2[middle2];
				}
				else
				{
					return findUpMiddleNumber(arr1, start1, middle1 - 1, arr2, middle2 + 1, end2);
				}
			}
			else
			{
				if (arr1[middle1] > arr2[middle2 - 1])
				{
					return arr1[middle1];
				}
				else
				{
					return findUpMiddleNumber(arr1, middle1 + 1, end1, arr2, start2, middle2 - 1);
				}
			}
		}
	}
}

static int findKthSmallerNumber(const int* arr1, const size_t size1, const int* arr2, const size_t size2, const int kth)
{
	const int* largerArr;
	const int* smallerArr;
	const size_t* largerSize;
	const size_t* smallerSize;
	if (size1 >= size2)
	{
		largerArr = arr1;
		smallerArr = arr2;
		largerSize = &size1;
		smallerSize = &size2;
	}
	else
	{
		largerArr = arr2;
		smallerArr = arr1;
		largerSize = &size2;
		smallerSize = &size1;
	}

	if (kth < *smallerSize)
	{
		return findUpMiddleNumber(largerArr, 0, kth, smallerArr, 0, kth);
	}
	else if (*smallerSize <= kth && kth < *largerSize)
	{
		int largerStart = kth - *smallerSize;
		int largerEnd = largerStart + *smallerSize;
		if (smallerArr[*smallerSize - 1] < largerArr[kth - *smallerSize])
		{
			return largerArr[kth - *smallerSize];
		}
		else
		{
			findUpMiddleNumber(largerArr, kth - *smallerSize + 1, kth, smallerArr, 0, *smallerSize - 1);
		}
	}
	else if (kth == *smallerSize + *largerSize - 1)
	{
		return smallerArr[*smallerSize - 1] > largerArr[*largerSize - 1] ? smallerArr[*smallerSize - 1] : largerArr[*largerSize - 1];
	}
	else
	{
		int lastCount = *smallerSize + *largerSize - kth;
		if (largerArr[*largerSize - lastCount] > smallerArr[*smallerSize - 1])
		{
			return largerArr[*largerSize - lastCount];
		}
		else if (smallerArr[*smallerSize - lastCount] > largerArr[*largerSize - 1])
		{
			return smallerArr[*smallerSize - lastCount];
		}
		else
		{
			return findUpMiddleNumber(largerArr, *largerSize - lastCount + 1, *largerSize - 1, smallerArr, *smallerSize - lastCount + 1, *smallerSize - 1);
		}
	}
}

/**
 * 给定两个一维int数组A和B。
 * 其中，A是长度为m、元素从小到大排好序的有序数组。B是长度为n、元素从小到大排好序的有序数组。希望从A和B数组中，找出最大的第k个数字，要求：使用尽量少的比较次数。
 * 
 * 思路：使用二分法，将时间复杂度控制为log(m)*log(n)
 * 需要用到一个算法：如何在两个等规模并且有序的数组中找到上中位数，即如果将两个有序长度为n的数组合为一个有序数组，n是偶数，则第n-1项是上中位数；n是奇数，则第n项是上中位数。
 * 
 * 比如:
 * [1  3  5  8]
 * [2  3  6  9]
 * 的上中位数是3。
 * 
 * [1  3  5  8]
 * [2  4  6  9]
 * 的上中位数是4。
 * 
 * [1  3  5  9  12]
 * [2  6  7  13 15]
 * 的上中位数是6.
 * 
 */
int main_findKthSmallerNumber()
{
	//int arr1[] = {1,3,5,9,13,15,20};
	//int size1 = sizeof(arr1) / sizeof(int);
	//int arr2[] = {2,6,8,10,11,14,17};
	//int size2 = sizeof(arr2) / sizeof(int);

	//int upMiddle = findUpMiddleNumber(arr1, 0, size1 - 1, arr2, 0, size2 - 1);
	//printf("%d\n", upMiddle);

	int arr3[] = {1,4,6,7,};
	int size3 = sizeof(arr3) / sizeof(int);
	int arr4[] = {2,5,8,10,};
	int size4 = sizeof(arr4) / sizeof(int);
	int kthLargest = 0;
	int res = findKthSmallerNumber(arr3, size3, arr4, size4, size4 + size3 - 1 - kthLargest);
	printf("%d\n", res);

	return 0;
}